package stru1.day2;

import java.util.Arrays;

/**
 * 88. 合并两个有序数组
 */
public class Solution2 {
    /**
     * 要求：合并后数组不应由函数返回，而是存储在数组 nums1 中。
     */
    public static void main(String[] args) {
        int[] nums1_1 = new int[]{1, 2, 3, 0, 0, 0};
        int[] nums1_2 = new int[]{2, 5, 6};
        merge(nums1_1, 3, nums1_2, 3);
        System.out.println(Arrays.toString(nums1_1));

        int[] nums2_1 = new int[]{1};
        int[] nums2_2 = new int[0];
        merge(nums2_1, 1, nums2_2, 0);
        System.out.println(Arrays.toString(nums2_1));

        int[] nums3_1 = new int[]{0};
        int[] nums3_2 = new int[]{1};
        merge(nums3_1, 0, nums3_2, 1);
        System.out.println(Arrays.toString(nums3_1));
    }

    /**
     * 对merge1的优化，由于nums1的长度是固定的(m+n),所以我们可以从尾部开始赋值，这样可以避免像头部赋值时那种的元素移动
     * 时间复杂度 O(n+m)
     * 空间复杂度 O(1)
     */
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1, p2 = n - 1; //nums1和nums2的尾指针（相对m和n）
        int tail = m + n - 1;//nums1的实际尾指针
        int cur;//当前操作元素
        while (p1 >= 0 || p2 >= 0) {
            if (p1 == -1) {
                cur = nums2[p2--];
            } else if (p2 == -1) {
                cur = nums1[p1--];
            } else if (nums1[p1] > nums2[p2]) {
                cur = nums1[p1--];
            } else {
                cur = nums2[p2--];
            }
            nums1[tail--] = cur; //赋值
        }
    }

    /**
     * 思路分析：从头遍历两个数组，依次比较，若nums2[temp]小于nums1[i]，则插入移动后面元素且移动指针
     * 时间复杂度 O((n+m)^2) ---> 实际速率要快一些，jvm对System.arraycopy有所增强
     * 空间复杂度 O(1)
     */
    public static void merge1(int[] nums1, int m, int[] nums2, int n) {
        int temp = 0; //遍历nums2的指针
        for (int i = 0; i < nums1.length; i++) { //遍历nums1
            if (i > m - 1) { //若nums1当前指针超过实际范围m，则直接赋值
                nums1[i] = nums2[temp];
                temp++;
            } else if (temp >= n) { //若nums2当前指针超过实际范围n，则返回
                return;
            } else if (nums2[temp] < nums1[i]) { //若nums2[temp]小于nums1[i]，则插入移动后面元素且移动指针
                System.arraycopy(nums1, i, nums1, i + 1, nums1.length - i - 1);
                nums1[i] = nums2[temp];
                temp++;
                m++;
            }
        }
    }
}
